home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / delete.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  6KB  |  202 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)delete.c    5.2 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <errno.h>
  44. #include <string.h>
  45. #include "btree.h"
  46.  
  47. /*
  48.  *  _BT_CRSRDEL -- Delete the item pointed to by the cursor.
  49.  *
  50.  *    This routine deletes the item most recently returned by a scan
  51.  *    through the tree.  Since it only makes sense to delete the current
  52.  *    record once, we make sure that we don't try to delete twice without
  53.  *    advancing the scan.
  54.  *
  55.  *    Parameters:
  56.  *        t -- tree in which to do deletion
  57.  *
  58.  *    Returns:
  59.  *        RET_SUCCESS, RET_ERROR.
  60.  *
  61.  *    Side Effects:
  62.  *        The call to _bt_delone marks the cursor, so we can tell that
  63.  *        the current record has been deleted.
  64.  */
  65.  
  66. int
  67. _bt_crsrdel(t)
  68.     BTREE_P t;
  69. {
  70.     CURSOR *c;
  71.  
  72.     c = &(t->bt_cursor);
  73.  
  74.     /* a cursor must exist, and can't have deleted the current key yet */
  75.     if (!(t->bt_flags & BTF_SEQINIT) || (c->c_flags & CRSR_BEFORE)) {
  76.         errno = EINVAL;
  77.         return (RET_ERROR);
  78.     }
  79.  
  80.     if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  81.         return (RET_ERROR);
  82.  
  83.     if (c->c_index >= NEXTINDEX(t->bt_curpage)) {
  84.         errno = EINVAL;
  85.         return (RET_ERROR);
  86.     }
  87.  
  88.     return (_bt_delone(t, c->c_index));
  89. }
  90.  
  91. /*
  92.  *  _BT_DELONE -- Delete a single entry from a btree.
  93.  *
  94.  *    This routine physically removes a btree entry from a leaf page.
  95.  *    IDATUM items are *never* removed from internal nodes, regardless
  96.  *    of whether the entries that originally caused them to be added
  97.  *    are removed from the tree or not.  In addition, pages made empty
  98.  *    by element deletion are not actually reclaimed.  They are,
  99.  *    however, made available for reuse.
  100.  *
  101.  *    To delete an item from a page, we pack the remaining items at
  102.  *    the end of the page, overwriting the deleted item's entry.  We
  103.  *    move the line pointers backward on the page, overwriting the
  104.  *    original item's line pointer.  This guarantees that the space in
  105.  *    the middle of the page is free -- a property that our insertion
  106.  *    strategy relies on.
  107.  *
  108.  *    This routine doesn't reclaim pages all of whose entries have
  109.  *    been deleted.  These pages are available for reuse, however.
  110.  *    If an item is deleted that was too big to fit on a page, then
  111.  *    the blocks that it occupies are put on a free list for reuse.
  112.  *
  113.  *    Parameters:
  114.  *        t -- btree from which to delete item
  115.  *        index -- index of entry on current page to delete
  116.  *
  117.  *    Returns:
  118.  *        RET_SUCCESS, RET_ERROR.
  119.  *
  120.  *    Side Effects:
  121.  *        Physically changes page layout, adjusts internal page
  122.  *        state to reflect the deletion of the item, and updates
  123.  *        the list of free pages for this tree.
  124.  */
  125.  
  126. int
  127. _bt_delone(t, index)
  128.     BTREE_P t;
  129.     index_t index;
  130. {
  131.     char *src, *dest;
  132.     int nbytes, nmoved;
  133.     index_t off;
  134.     index_t top;
  135.     index_t i;
  136.     pgno_t chain;
  137.     BTHEADER *h;
  138.     CURSOR *c;
  139.     DATUM *d;
  140.  
  141.     /* deletion may confuse an active scan.  fix it.  */
  142.     c = &(t->bt_cursor);
  143.     if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
  144.         if (_bt_fixscan(t, index, (DATUM *) NULL, DELETE) == RET_ERROR)
  145.             return (RET_ERROR);
  146.  
  147.     h = t->bt_curpage;
  148.     off = h->h_linp[index];
  149.     d = (DATUM *) GETDATUM(h, index);
  150.  
  151.     /* if this is a big item, reclaim the space it occupies */
  152.     if (d->d_flags & D_BIGKEY) {
  153.         bcopy(&(d->d_bytes[0]),
  154.               (char *) &chain,
  155.               sizeof(chain));
  156.         if (_bt_delindir(t, chain) == RET_ERROR)
  157.             return (RET_ERROR);
  158.         h = t->bt_curpage;
  159.         d = (DATUM *) GETDATUM(h, index);
  160.     }
  161.     if (d->d_flags & D_BIGDATA) {
  162.         bcopy(&(d->d_bytes[d->d_ksize]),
  163.               (char *) &chain,
  164.               sizeof(chain));
  165.         if (_bt_delindir(t, chain) == RET_ERROR)
  166.             return (RET_ERROR);
  167.         h = t->bt_curpage;
  168.         d = (DATUM *) GETDATUM(h, index);
  169.     }
  170.  
  171.     /* move the data down on the page */
  172.     nbytes = d->d_ksize + d->d_dsize
  173.          + (sizeof(DATUM) - sizeof(char));
  174.     nbytes = LONGALIGN(nbytes);
  175.     src = ((char *) h) + h->h_upper;
  176.     dest = src + nbytes;
  177.     nmoved = (int) (((char *) d) - src);
  178.     (void) bcopy(src, dest, nmoved);
  179.  
  180.     /* next move the line pointers up */
  181.     src = (char *) &(h->h_linp[index + 1]);
  182.     dest = (char *) &(h->h_linp[index]);
  183.     nmoved = (int) (((char *) &(h->h_linp[NEXTINDEX(h)])) - src);
  184.     (void) bcopy(src, dest, nmoved);
  185.  
  186.     /* remember that we freed up some space */
  187.     h->h_upper += nbytes;
  188.     h->h_lower -= sizeof(index_t);
  189.  
  190.     /* adjust offsets in line pointers affected by moving the data */
  191.     top = NEXTINDEX(h);
  192.     for (i = 0; i < top; i++) {
  193.         if (h->h_linp[i] < off)
  194.             h->h_linp[i] += nbytes;
  195.     }
  196.  
  197.     /* it's gone */
  198.     h->h_flags |= F_DIRTY;
  199.  
  200.     return (RET_SUCCESS);
  201. }
  202.